Technical Field
The present invention relates to an image processing apparatus for extracting a predetermined target region from an image, and an operation method and a program therefor.
Background Art
Hitherto, a method of formulating segmentation of an image as an energy minimization problem, and solving the energy minimization problem by using a graph cut algorithm has been known. For example, segmentation of the image may be posed as a problem of assigning a value (label) of 0 or 1 representing belonging to a target region or belonging to another region to each variable x1, x2, . . . xn corresponding to each pixel in the image, and a quadratic energy function E such as that represented by Expression (1), in which energy decreases as the assigning (i.e., the labeling) becomes more desirable, is defined to determine a solution that minimizes the quadratic energy function E.
                              [                      Math            .                                                  ⁢            1                    ]                ⁢                                                                                                E          ⁡                      (                                          x                i                            ,              …              ⁢                                                          ,                              x                n                                      )                          =                                            ∑              i                        ⁢                                          E                i                            ⁡                              (                                  x                  i                                )                                              +                                    ∑                              (                                  i                  ,                  j                                )                                      ⁢                                          E                ij                            ⁡                              (                                                      x                    i                                    ,                                      x                    j                                                  )                                                                        (        1        )            
As a method of solving such a minimization problem, in C. Rother, et al., “Optimizing Binary MRFs via Extended Roof Duality”, CVPR, pp. 1-8, 2007 (hereinafter Non-Patent Literature 1), there is proposed a method of globally determining a solution using a minimum cut algorithm when energy is submodular, and determining an optimal solution or an approximate solution using a quadratic pseudo-Boolean optimization (QPBO) algorithm when energy is non-submodular.
Further, in C. Rother, et al., “Minimizing Sparse Higher Order Energy Functions of Discrete Variables”, CVPR, pp. 1-8, 2009 (hereinafter Non-Patent Literature 2), there is proposed a method of solving a minimization problem of a third order or higher energy function by converting the minimization problem into an equivalent minimization problem of a quadratic energy function. In P. Kohli et al., “Robust Higher Order Potentials for Enforcing Label Consistency”, International Journal of Computer Vision archive, Vol. 82, No. 3, pp. 302-324, 2009 (hereinafter Non-Patent Literature 3), there is proposed a method in which segmentation of an image is provided with robustness by, when defining high order submodular energy, setting the values of higher-order terms to be at a minimum value when the same label is assigned to all of the variables, so that energy gradually increases along with an increase in the number of variables assigned to different labels.